/**
 * 给你一个二叉树的根结点root，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
 *
 * 一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
 *https://leetcode.cn/problems/most-frequent-subtree-sum/
 */
class FindFrequentTreeSum {
    Map<Integer,Integer> map=new HashMap<>();
    int maxCount=0;
    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        List<Integer> ret=new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            int s=entry.getKey();
            int n=entry.getValue();
            if(n==maxCount){
                ret.add(s);
            }
        }
        int size=ret.size();
        int[] ans=new int[size];
        for(int i=0;i<size;i++){
            ans[i]=ret.get(i);
        }
        return ans;
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int right=dfs(root.right);
        int left=dfs(root.left);
        int sum=left+right+root.val;
        map.put(sum,map.getOrDefault(sum,0)+1);
        maxCount=Math.max(maxCount,map.get(sum));
        return sum;
    }
}